using System;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Data.Linq;


namespace adt.tree
{
	public class Tree<T>
	{
		public T Root { set; get; }
		public IList<Tree<T>> Subtrees { set; get; }
		
		public Tree() : this(default(T)) { }
		
		public Tree(T root)
		{
			Root = root;
			Subtrees = new List<Tree<T>>();
		}
		
		public Tree(T root, Tree<T>[] subtrees)
		{
			Root = root;
			Subtrees = new List<Tree<T>>(subtrees);
		}
		
		public Tree(T root, IList<Tree<T>> subtrees)
		{
			Root = root;
			Subtrees = subtrees;
		}
		
		public override String ToString()
		{
			StringBuilder b = new StringBuilder();
			b.Append(Root); 
			if (Subtrees.Count > 0) {
				b.Append("{");
				new ui.text.TextList(Subtrees).Join(",",b);
				b.Append("}");
			}
			return b.ToString();
		}
		
		public override bool Equals(object obj)
		{
			if (obj is Tree<T>) {
				var other = obj as Tree<T>;
				return Root.Equals(other.Root) && Subtrees.SequenceEqual(other.Subtrees);
			}
			else {
				return false;
			}
		}
		
		public override int GetHashCode()
		{
			return Root.GetHashCode(); // @@ not efficient, but semantically correct
		}
	}
	
	/**
	 * An assistant class for building trees in your code using sequence
	 * initializers.
	 */
	public class BuildTree<T, TreeT> : IEnumerable where TreeT : Tree<T>, new()
	{
		private TreeT tree;
		private List<TreeT> path;
		
		public BuildTree()
		{
			tree = new TreeT();
			path = new List<TreeT>() { tree };
		}
		
		public TreeT Tree { get { return (TreeT)tree.Subtrees[0]; } }
		
		private TreeT cursor { get { return path[path.Count - 1]; }}
		
		public void Add(T a) {
			var s = new TreeT() { Root = a };
			cursor.Subtrees.Add(s);
		}
		public void Add(char c) {
			if (c == '{') {
				var s = cursor.Subtrees;
				if (s.Count == 0)
					throw new ArgumentException("malformed tree at " + tree);
				path.Add((TreeT)s[s.Count - 1]);
			}
			else if (c == '}') {
				path.RemoveAt(path.Count - 1);
			}
		}
		
		// dummy
		IEnumerator IEnumerable.GetEnumerator() { return null; }		
	}
	
	class BuildTree<T> : BuildTree<T, Tree<T>> { }
}

